package java0322;

import java.util.Arrays;

public class MyPriorityQueue {
    // 属性
    private int[] arr = new int[100];
    private int size = 0;
    // 向下调整 大堆
    // 前提条件, 要求当前被调整节点的左右子树都已经是堆了
    // 方法参数给出了一个 size 表示当前数组的有效元素大小.
    // 虽然可以通过 arr.length 取到大小, 这个大小是数组的总的大小
    // index 表示从这个位置开始进行向下调整
    // 还是按照大堆的方式来实现.
    // 时间复杂度 O(logN)
    // 如果数据是依次 * 2 / 2 的方式变化的时候, 时间复杂度基本都和 logN 相关

    // MaxSize 为最大容量
    public MyPriorityQueue(int MaxSize) {
        arr = new int[MaxSize];
        size = 0;
    }

    // 根据传入数组构造
    public MyPriorityQueue(int[] arr) {
        size = arr.length;
        // 最大容量改为传入数组的二倍
        this.arr = new int[2 * size];
        // 将数组中的值填入堆中
        int index = 0;
        for (int x : arr) {
            this.arr[index] = x;
            index++;
        }
        // 采用向上调整
        for (index = 0; index < size; index++) {
            shiftUp(index);
        }
//        // 或者向下调整，只需要从最后一个节点的父亲节点开始调整即可
//        for (index = (size - 1) / 2; index >= 0; index--) {
//            shiftDown(index);
//        }
    }

    // 向下调整
    // 私有方法，在外部不调用
    private void shiftDown(int index) {
        int parent = index;
        int child = 2 * parent + 1;
        while (parent < size) {
            // 两个孩子都不存在，直接结束
            if (child >= size) {
                break;
            }
            // 左右孩子都存在，开始调整
            if (child + 1 < size) {
                // 如果父亲比左右孩子都大,说明调整完成
                if (arr[parent] >= arr[child] && arr[parent] >= arr[child + 1]) {
                    break;
                }
                int tmp = arr[parent];
                if (arr[parent] > arr[child]) {
                    arr[parent] = arr[child + 1];
                    arr[child + 1] = tmp;
                    parent = child + 1;
                }else if (arr[parent] > arr[child + 1]) {
                    arr[parent] = arr[child];
                    arr[child] = tmp;
                    parent = child;
                }else {
                    if (arr[child] > arr[child + 1]) {
                        arr[parent] = arr[child];
                        arr[child] = tmp;
                        parent = child;
                    }else {
                        arr[parent] = arr[child + 1];
                        arr[child + 1] =tmp;
                        parent = child + 1;
                    }
                }
                // 只存在左孩子
            }else {
                if (arr[parent] >= arr[child]) {
                    break;
                }else {
                    int tmp = arr[parent];
                    arr[parent] = arr[child];
                    arr[child] = tmp;
                    parent = child;
                }
            }
            child = 2 * parent + 1;
        }
    }

    // 向上调整
    public void shiftUp(int index) {
        int child = index;
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            if (arr[child] > arr[parent]) {
                int tmp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = tmp;
            }else {
                break;
            }
            child = parent;
            parent = (child - 1) / 2;
        }
    }

//    // 建堆操作,采用向上调整的方法
//    public void createHeap1(int[] array) {
//        for (int i = 0; i < array.length; i++) {
//            shiftUp(array, array.length, i);
//        }
//    }

    // 建堆操作，采用向下调整的方法
//    public static void createHeap2(int[] array) {
//        int index = (array.length - 1) / 2;
//        for (int i = index; i >= 0; i--) {
//            shiftDown(array, array.length, i);
//        }
//    }

    // 插入操作
    public void offer(int val) {
        if (size >= arr.length) {
            System.out.println("空间已满插入失败");
            return;
        }
        size++;
        arr[size - 1] = val;
        shiftUp(size - 1);
    }

    // 获取堆顶元素
    public Integer peek() {
        if (size == 0) {
            return null;
        }
        return arr[0];
    }

    // 删除堆顶元素
    public Integer poll() {
        if (size == 0) {
            return null;
        }
        int ret = arr[0];
        size--;
        arr[0] = arr[size];
        shiftDown(0);
        return ret;
    }

    // 判断是否为空
    public boolean isEmpty() {
        return size == 0 ? true : false;
    }

    public static void main(String[] args) {
//        int[] arr = {99,90,22,82,94,11,19,13,17,92,93};
//        shiftDown(arr, 11, 1);
//        System.out.println(Arrays.toString(arr));
        int[] arr = {1,8,3,11,5,12,15,8,9};
        MyPriorityQueue myPriorityQueue = new MyPriorityQueue(arr);
        myPriorityQueue.offer(5);
        System.out.println("堆顶元素为" + myPriorityQueue.peek());
        while (myPriorityQueue.isEmpty() == false) {
            System.out.print(myPriorityQueue.poll() + " ");
        }
    }
}
